#include <string.h>
#include <string>
#include <sstream>
#include <queue>
#include <stack>
#include <math.h>
#include <unordered_map>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

#define INT_MAX 0x7fffffff
#define MAXSIZE 1000
// #define INTMAX 2147483647
// #define INTMIN -2147483648

// 顺序表结构体
typedef struct SqList
{
    int data[MAXSIZE];
    int length;
} SqList;

// 单链表结构体
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

// 顺序栈
typedef struct SqStack
{
    int top;
    char data[MAXSIZE];
} SqStack;
typedef struct ISqStack
{
    int top;
    int data[MAXSIZE];
} ISqStack;

// 链栈 出战相当于去掉第一个结点，入栈：头插法插入结点
typedef struct LStack
{
    struct LNode *next;
    char data;
} LStack;

// 顺序表创建的队列
typedef struct SQueue
{
    int data[MAXSIZE];
    int front, rear;
} SQueue;

// 顺序表创建带tag的队列
typedef struct STQueue
{
    int tag;
    int data[MAXSIZE];
    int front, rear;
} STQueue;

// 链表创建队列
typedef struct LQueue
{
    LNode *front, *rear;
} LQueue;

typedef struct DLNode
{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
} BLNode;

typedef struct DLNodeF
{
    int data;
    int freq = 0;
    struct DLNodeF *prior;
    struct DLNodeF *next;
} DLNodeF;

typedef struct DFreqLNode
{
    int data;
    int freq;
    struct DFreqLNode *pre;
    struct DFreqLNode *next;
} DFreqLNode;

// 二叉链表
typedef struct BTNode
{
    char data; // 存放数据
    BTNode *lChild, *rChild;
} BTNode;

// 线索二叉树： 相较于二叉树，线索二叉数多了ltag和rtag,用于标记该结点的左孩子和右孩子是否为空，是则为1，否为0，
typedef struct TBTNode
{
    char data;
    TBTNode *lChild;
    TBTNode *rChild;
    int ltag;        //ltag = 0,表示lChild指向孩子, =1表示指向时线索
    int rtag;        //rtag = 0,表示rChild指向孩子, =1表示指向时线索
} TBTNode;

// 哈夫曼树HTNode 结点的带权路径长度，从树的根到该结点的路径长度 * 该结点的权值
// 树的带权路径长度：树种所有叶结点的带权路径长度之和
typedef struct HTNode
{
    int weight; // 结点的权，某种含义的数量（如重要性）
    TBTNode *parent, *lChild, *rChild;
} HTNode;